package 字符串匹配算法;

/**
 * @Project: data-structure-and-algorithms
 * @Package: 字符串匹配算法
 * @ClassName: BruteForce
 * @Author: zhouyihe
 * @Date: 2025/11/17 14:40
 * @Description: BF算法，也叫朴素匹配算法，暴力匹配
 */
public class BruteForce {
    public static int bruteForce(String text, String pattern) {
        int m = text.length();
        int n = pattern.length();


        int i = 0, j = 0;
        while (i < m && j < n) {
            if (text.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
            } else {
                i = i - j + 1;
                j = 0;
            }
        }

        if (j == n) {
            return i - j;
        } else {
            return -1;
        }

    }

    // 打印结果
    public static void main(String[] args) {
        String text = "ABABCABABDABACDABABCABAB";
        String pattern = "ABABCABAB";

        int position = bruteForce(text, pattern);
        if (position == -1) {
            System.out.println("未找到匹配");
        } else {
            System.out.println("模式串在位置 " + position + " 处匹配");
            System.out.println(text);
            // 打印指示匹配位置的指针
            for (int i = 0; i < position; i++) {
                System.out.print(" ");
            }
            System.out.println(pattern);
        }
    }
}
